<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
<script>
    /*
    * 上楼梯：
    *   小明在楼梯第0阶，现在要上到第n阶
    *   小明一共有两种上楼梯的方式，一次上两阶，一次上三阶，
    *   设计一个函数，计算小明上到第n阶的走法数
    *   提示：
    *   理解清楚你设计的函数的意义
    *   将函数转化成 简单的问题
    *   将最基础的情况即结束条件判断出来
    *
    *   假设上到第5阶
    *   n = 5 => 2+3=5 / 3+2=5
    *   所以有两种走法：f(5)=2
    *
    *   假设上到第6阶
    *   n = 6 => 2+2+2=6 / 3+3=6
    *   所以有两种走法：f(6)=2
    *
    *   假设上到第8阶
    *   n = 8 是怎么走的？
    *   只能从哪个位置走到第8阶？因为小明一次只能跨2阶 或者只能一次跨3阶
    *   所以有
    *   从第5阶 +3 到第8阶 想一想 从第5阶到第8阶 除了+3有其他走法吗？ 所以到第5阶的走法数 决定了走到第8阶的走法数
    *   从第6阶 +2 到第8阶 想一想 从第6阶到第8阶 除了+2有其他走法吗？ 所以到第6阶的走法数 决定了走到第8阶的走法数
    *   所以 走到第8阶的走法数 = 走到第5阶的走法数 + 走到第6阶的走法数
    *   即 f(8) = f(5) + f(6)
    *   由此我们可以推导出
    *   走到第n阶的走法数 = 走到第(n-3)阶的走法数 + 走到第(n-2)阶的走法数  (设计的函数的意义)
    *   f(n) = f(n-3) + f(n-2)  (转化成简单的问题)
    *   f(1) = 0
    *   f(2) = 1
    *   f(3) = 1
    *   f(4) = 1 => f(1) + f(2)
    *   f(5) = 2 => f(2) + f(3)
    *   f(6) = 2 => f(3) + f(4)
    *   f(7) = 3 => f(4) + f(5)
    *   f(8) = 4 => f(5) + f(6)
    *
    * */
    let resultMap = [] //生成一个记录表，记录曾经计算过的结果

    function f(n){ //如果没有记录曾经的计算结果 会很消耗性能 函数fn是这个函数的优化版
        if(n <= 1) return 0 //结束条件
        if(n <= 3) return 1 //结束条件
        return f(n-2) +f(n-3)
    }

    function fn(n){ //如果没有记录曾经的计算结果 会很消耗性能
        if(resultMap[n]) return resultMap[n] //如果所计算的内容已经被记录在记录表中，就直接在记录表中查询
        if(n <= 1){ //结束条件 结束的是小于等于1阶的情况
            resultMap[n] = 0 //如果n小于等于1阶且计算的结果不在记录表中，将计算结果赋值为0并在表中记录下来
            return resultMap[n] //将计算结果的值返回出去
        }
        if(n <= 3){ //结束条件 结束的是小于等于3阶的情况
            resultMap[n] = 1 //如果n小于等于3阶且计算的结果不在记录表中，将计算结果赋值为1并在表中记录下来
            return resultMap[n] //将计算结果的值返回出去
        }
        resultMap[n] = fn(n-2) +fn(n-3) //记录的是n大于3阶的情况 递归函数一步步分解成了最基本情况 只要算出最基本情况 就能一步步倒推出第n阶的情况
        return resultMap[n] //将最终的计算结果return出去
    }
    //fn函数的记录表非常强悍，如果直接算到第150阶的走法数情况，会将150阶之前的所有情况都记录表中，除了第149阶的情况，因为fn(150)= fn(147)+fn(148)
    //计算fn(149)对于fn(150)没有任何作用，所以没有记录第149阶的情况



</script>
</body>
</html>